/**
 * 最少硬币找零问题的一个变种 硬币找零问题是给出要找零的钱数 以及可用的硬币面额d1...dn及其数量 找出有多少种找零方法 最少硬币找零问题是给出要找零的钱数
 * 以及可用的硬币面额d1..dn及其数量 找到所需的最少的硬币个数
 */
// 美国有以下面额（硬币）：d1=1，d2=5，d3=10，d4=25。 
// 如果要找36美分的零钱，我们可以用1个25美分、1个10美分和1个便士（1美分）。 
// 如何将这个解答转化成算法
/**
 * 
 * @param {*} coins 面额 例如[1,5,10,25]
 */
function MinCoinChange (coins) {
  var coins = coins // 1. 包含硬币面额的数组
  var cache = {} // 2. 用于存储已计算结果的缓存对象
  this.makeChange = function (amount) { // amount 零钱
    var me = this
    if (!amount) { // 3如果amount不为正 返回空数组
      return []
    }
    if (cache[amount]) { // 如果缓存中存在amount对应的结果 直接从缓存中返回结果 避免重复计算
      return cache[amount]
    }
    var min = [], newMin, newAmount
    for (var i = 0; i < coins.length; i++) { // 5 遍历硬币数组 对每个硬币进行处理
      var coin = coins[i]
      newAmount = amount - coin // 6 计算剩余金额
      console.log(newAmount);
      if (newAmount >= 0) { // 剩余金额大于等于0 递归调用makeChange 函数来计算剩余金额的最小硬币数
        newMin = me.makeChange(newAmount) // 7
      } // 8 9 10
      // 如果剩余金额大于等于0 并且新的的最小硬币数newMin的长度比当前最小硬币数min的长度小 或者当前最小硬币数为空数组 并且
      // 新的最小硬币数的长度不为0 或者剩余金额为0 则更新最小硬币数min
      if (newAmount >= 0 && (newMin.length < min.length - 1 || !min.length) && (newMin.length || !newAmount)) {
        min = [coin].concat(newMin)
        // console.log('new min' + min + 'for' + amount); // 11 输出最小硬币数和对应的金额
      }
    }

    return (cache[amount] = min) // 将当前硬币加入最小硬币数min的开头并返回结果 同时将结果存入缓存中
  }
}
var minCoinChange = new MinCoinChange([1, 5, 10, 25])
console.log(minCoinChange.makeChange(36));